from functools import wraps

# E: everyone's height, S: length of all skateboards
E = [5, 7, 8, 9, 10]
S = [1, 2, 4, 5, 6, 7, 9, 11, 12]

# E = [1, 5, 7]
# S = [1, 4, 5, 9]

E = list(sorted(E))
S = list(sorted(S))

n = len(E)
m = len(S)
inf = float('inf')

E.insert(0, 0)
S.insert(0, 0)

record = {}


def memo(func):
    cache = record

    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]

    return wrap


@memo
def compute_c(i, j):
    if 0 in (i, j) and i <= j:
        return 0
    elif i > j >= 0:
        return inf
    elif 1 <= i <= j:
        return min(compute_c(i, j - 1), compute_c(i - 1, j - 1) + abs(E[i] - S[j]))


weight = compute_c(n, m)
print('Min:', weight)

targets = []
remain_weight = weight
limit = m

for index, x in enumerate(range(n)):
    r_i = n - index
    pos = min([k[1] for k, v in record.items() if v == remain_weight and k[0] == r_i and k[1] <= limit])
    targets.insert(0, pos)
    remain_weight -= abs(E[r_i] - S[pos])
    limit = pos - 1

print('Map:', [x for x in zip(E[1:], [S[i] for i in targets])])